package algoritmos;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;
import logica.ComparadorCosto;
import logica.Matriz;
import logica.Nodo;

/**
**********************************************************************************************<br/>
* Aplico un algoritmos ingenuo donde consistente <br/>
* en generar cada alternativa posible, calcular su
* costo y escoger la mejor.
* @author Jefferson Amado Pe&ntilde;a Torres
* @author Cristian H. Alzate
**********************************************************************************************
* @version 1.00 2010/11/10
*/
public class AlgoritmoOptimo implements Algoritmos{
    private Queue<Nodo> cola;
    private ArrayList<Nodo> soluciones;
    private int filas;
    private int columnas;
    private int[][] entrada;
    private int[] costos;
    private int[] objetivos;

    public AlgoritmoOptimo(int[][] entrada, int[] costos, int[] objetivos){
        this.entrada=entrada;
        this.costos=costos;
        this.objetivos=objetivos;
         Comparator<Nodo> comparador= new ComparadorCosto();
        cola = new PriorityQueue<Nodo>(10,comparador);
        soluciones = new ArrayList<Nodo>(objetivos.length);
        filas=entrada.length;
        columnas=entrada[0].length;
    }

    public void crearSolucion(){
        for(int cont=0;cont<objetivos.length;cont++){
            //el nodo origen en la cola
            ArrayList<Integer> metas = inicializarCola(objetivos.length-cont);
            cola.clear();
            int inicio=metas.get(0);
            cola.add(new Nodo(inicio,null,0));
            boolean bucle=true;

            while(bucle){
                Nodo actual = cola.peek();
                for(int i=0;i<metas.size();i++){

                    if(metas.size()>0)
                    if(actual.getNombre()==metas.get(i)){
                        soluciones.add(actual);
                        metas.remove(i);
                    }
                }

                if(metas.size()>0)
                    expandir(actual);

                else
                    bucle=false;
            }
        }
    }

    private ArrayList<Integer> inicializarCola(int tamano){
        ArrayList<Integer> metas = new ArrayList<Integer>(tamano);
        //metas.clear();
        for(int i=0;i<tamano;i++)
            metas.add(objetivos[(objetivos.length-tamano)+i]-1);

        return metas;
    }

    private void expandir(Nodo padre){
        int inicio=padre.getNombre();
        Nodo actual = padre;
        for(int j=0;j<columnas;j++){
            if(entrada[inicio][j]==1)
            {
                for(int x=0;x<filas;x++){//inicio+1
                    if(x<filas&&x!=inicio)
                    if(entrada[x][j]==1){
                        cola.add(new Nodo(x,actual,actual.getCosto()+costos[j]));
                        x=filas;
                    }
                }
            }
        }
        cola.poll();
    }

    public void pintarRutas(){
        for (int i=0;i<soluciones.size();i++){
            pintarRuta(soluciones.get(i));
            System.out.println(" ");
        }
    }

    public String pintarRuta(Nodo p){
        if(p!=null)
            System.out.print(pintarRuta(p.getPadre())+" "+p.getNombre());

        return "";
    }

    public String obtenerRuta(Nodo p){
        if(p.getPadre()==null)
           return ""+p.getNombre();

        else
            return(obtenerRuta(p.getPadre())+" "+p.getNombre());
    }

    public int[][] getSolucion(){
        ArrayList<int[][]> matrices = new ArrayList<int[][]>(objetivos.length);
        Matriz m=new Matriz();

        int[][] salida =m.Matriz(filas);
        for(int i=0;i<soluciones.size();i++){
          //  int ix=0;

            String miniruta= obtenerRuta(soluciones.get(i));
            String[] minirutaArray=miniruta.split(" ");

            if(minirutaArray.length>2){
                for(int j=0;j<((minirutaArray.length-1));j++){
                    int a=Integer.parseInt(minirutaArray[j]);
                    int b=Integer.parseInt(minirutaArray[j+1]);
                    if(salida[a][b]!=1){
                    salida[a][b]=1;
                    }
                }
            }
        }

        return salida;
    }

    
		

}
